from math import ceil, sqrt
import random


class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        ans = 0
        z = [-1]  # 左侧填个假0，用于结算左侧只有1没有0的那些1，如110
        # 以i为子串右界，枚举左界，因为数据量范围不能每个左界都枚举，可以枚举0，0最多不超过200个，凑一起最多8*10^6，刚刚好
        # ...0....0....0...0...0....0....i....
        # 大思路：左边每两个0中间的1，有多少可以成为i的左界
        # ...0....0....0...z[j]....p0....0....i....
        # 转移：从i到前一个0，即[p0,i]之间，累计0的数量和1的数量，差多少个1？[z[j],p0]中间有多少个1填这个差，剩下的1就可以作为左界
        # 这个差值计算是可以O(1)完成的
        # 最后检查z[j]这个0为左界的子串[z[j],i]是否满足要求
        for i, v in enumerate(s):
            if v == "0":
                z.append(i)
            # t0 累计0的数量，t1累计1的数量，p0前一个0的位置
            t0, t1, p0 = 0, 0, i + 1
            # for j in range(len(z) - 1, max(-1, len(z) - 1 - ceil(sqrt(i + 1))), -1):
            for j in range(len(z) - 1, max(-1, len(z) - 200), -1):
                s1 = p0 - z[j] - 1  # 上一个0到这个0中间1的数量
                # 需要补充1的数量,t0 * t0 - t1个1刚好达到条件，那么t0 * t0 - t1 -1 个1不能成为左边界
                d1 = t0 * t0 - t1 - 1
                # max(0, d1) d1小于0的时候说明1很多，不需要s1中的1填坑
                # s1 - max(0, d1) 小于0说明s1都填了也不够，能作为左边界的1数量为0，取max(s1 - max(0, d1), 0)
                ans += max(s1 - max(0, d1), 0)
                t1 += s1  # 增加1的数量
                t0 += 1  # 增加0的数量
                # 检查这个边界0是否是有效的
                if j > 0 and t0 * t0 <= t1:
                    ans += 1
                p0 = z[j]

        return ans


s = Solution()
print(s.numberOfSubstrings("101101"))
print(s.numberOfSubstrings("00011"))
c = []
for _ in range(40000):
    c.append(str(random.randint(0, 1)))
# print("".join(c))
